using System;
using System.Collections.Generic;
using Kopernikus.Collections.Generic;

namespace Kopernikus.Parsing.Earley
{
    public class EarleyChart<T, S>
    {
        private readonly EarleyDFA m_dfa;
        private readonly IGrammar m_grammar;

        private readonly Dictionary<EarleySetItem, List<EarleyLink>> m_links =
            new Dictionary<EarleySetItem, List<EarleyLink>>();

        private readonly List<Set<EarleyItem>> m_sets = new List<Set<EarleyItem>>();
        private readonly List<T> m_tokens = new List<T>();

        public EarleyChart(IGrammar grammar, EarleyDFA dfa)
        {
            m_grammar = grammar;
            m_dfa = dfa;
        }

        public List<Set<EarleyItem>> Sets
        {
            get { return m_sets; }
        }

        public List<T> Tokens
        {
            get { return m_tokens; }
        }

        public IEnumerable<EarleySetItem> GetSetItems(int setIndex)
        {
            foreach (EarleyItem item in m_sets[setIndex])
            {
                yield return EarleySetItem.Create(item, setIndex);
            }
        }

        public EarleySetItem AddSetItem(int setIndex, int itemState, int itemParent)
        {
            return EarleySetItem.Create(m_sets[setIndex].Add(EarleyItem.Create(itemState, itemParent)), setIndex);
        }

        private static Production Disambiguate(Set<Production> completed, IEarleyEvaluator<T, S> evaluator)
        {
            return evaluator.Disambiguate(completed);
        }


        public S BuildTree(IEarleyEvaluator<T, S> evaluator, EarleySetItem item)
        {
            Set<Production> completed = m_dfa.Completed(item.Item.State);
            if (completed.Count == 1)
            {
                foreach (Production production in completed)
                {
                    return BuildTree(evaluator, production, item);
                }
            }
            else if (completed.Count > 1)
            {
                Production production = Disambiguate(completed, evaluator);
                return BuildTree(evaluator, production, item);
            }
            throw new ApplicationException("Internal error");
        }

        public S BuildTree(IEarleyEvaluator<T, S> evaluator, Production production, EarleySetItem item)
        {
            S[] operands = new S[production.RHS.Length];
            for (int operandIndex = production.RHS.Length - 1; operandIndex >= 0; --operandIndex)
            {
                Symbol symbol = production.RHS[operandIndex];
                if (m_grammar.SymbolSets.NullableSymbols.Contains(symbol))
                {
                    operands[operandIndex] = evaluator.ReduceEmpty(symbol);
                }
                else if (m_grammar.SymbolSets.TerminalSymbols.Contains(symbol))
                {
                    operands[operandIndex] = evaluator.Shift(m_tokens[item.SetIndex - 1]);
                    item = GetPredecessorLink(item, EarleySetItem.None);
                }
                else
                {
                    EarleySetItem itemWhy = GetCausalLink(item, evaluator);
                    operands[operandIndex] = BuildTree(evaluator, itemWhy);
                    item = GetPredecessorLink(item, itemWhy);
                }
            }
            return evaluator.Reduce(production, operands);
        }

        public void AddLink(EarleySetItem item, EarleySetItem predecessor, EarleySetItem causal)
        {
            List<EarleyLink> links;
            if (!m_links.TryGetValue(item, out links))
            {
                links = new List<EarleyLink>();
                m_links.Add(item, links);
            }
            links.Add(EarleyLink.Create(predecessor, causal));
        }

        private EarleySetItem GetPredecessorLink(EarleySetItem item, IEquatable<EarleySetItem> causal)
        {
            List<EarleyLink> links;
            if (m_links.TryGetValue(item, out links))
            {
                foreach (EarleyLink link in links)
                {
                    if (causal.Equals(link.Causal))
                    {
                        return link.Predecessor;
                    }
                }
                //return links[0].Predecessor;
            }
            //return EarleySetItem.None;
            throw new ApplicationException("Internal error");
        }

        private EarleySetItem GetCausalLink(EarleySetItem item, IEarleyEvaluator<T, S> evaluator)
        {
            List<EarleyLink> links;
            if (m_links.TryGetValue(item, out links))
            {
                if (links.Count == 1)
                {
                    return links[0].Causal;
                }

                // NOTE: [[ Improvisation
                //List<EarleyLink> causalLinks = links.FindAll(delegate(EarleyLink l) { return !l.Causal.Item.Equals(EarleyItem.None); });
                //if (causalLinks.Count == 1)
                //{
                //    return causalLinks[0].Causal;
                //}
                // NOTE: Improvisation ]]

                Dictionary<Production, int> causalProductions = new Dictionary<Production, int>();
                int i = 0;
                foreach (EarleyLink link in links)
                {
                    foreach (Production causalProduction in m_dfa.Completed(link.Causal.Item.State))
                    {
                        if (!causalProductions.ContainsKey(causalProduction))
                        {
                            causalProductions.Add(causalProduction, i);
                        }
                    }
                    ++i;
                }

                int resolvedIndex;
                if (causalProductions.Count == 1)
                {
                    resolvedIndex = 0;
                }
                else
                {
                    Set<Production> completedProductions = new Set<Production>(causalProductions.Keys);
                    Production production = Disambiguate(completedProductions, evaluator);
                    resolvedIndex = causalProductions[production];
                }

                return links[resolvedIndex].Causal;
            }
            return EarleySetItem.None;
        }
    }
}